{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Happy Prefix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #string-matching #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #字符串匹配 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestPrefix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长快乐前缀"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>「快乐前缀」</strong>&nbsp;是在原字符串中既是&nbsp;<strong>非空</strong> 前缀也是后缀（不包括原字符串自身）的字符串。</p>\n",
    "\n",
    "<p>给你一个字符串 <code>s</code>，请你返回它的 <strong>最长快乐前缀</strong>。如果不存在满足题意的前缀，则返回一个空字符串<meta charset=\"UTF-8\" />&nbsp;<code>\"\"</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"level\"\n",
    "<strong>输出：</strong>\"l\"\n",
    "<strong>解释：</strong>不包括 s 自己，一共有 4 个前缀（\"l\", \"le\", \"lev\", \"leve\"）和 4 个后缀（\"l\", \"el\", \"vel\", \"evel\"）。最长的既是前缀也是后缀的字符串是 \"l\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ababab\"\n",
    "<strong>输出：</strong>\"abab\"\n",
    "<strong>解释：</strong>\"abab\" 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 只含有小写英文字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-happy-prefix](https://leetcode.cn/problems/longest-happy-prefix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-happy-prefix](https://leetcode.cn/problems/longest-happy-prefix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"level\"', '\"ababab\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        MOD = 10**9+7   # 模底\n",
    "        base = 31       # 进制\n",
    "        mul = 1         # 存储base的幂\n",
    "        \n",
    "        '''字符编码'''\n",
    "        def encode(ch):\n",
    "            return ord(ch) - ord('a') + 1\n",
    "\n",
    "        prefix, suffix = 0, 0\n",
    "        n = len(s)\n",
    "        happy = 0\n",
    "        for i in range(n-1):\n",
    "            prefix = ( prefix * base + encode(s[i]) ) % MOD     # 前缀哈希\n",
    "            suffix = ( suffix + encode(s[n-1-i]) * mul ) % MOD  # 后缀哈希\n",
    "            mul = mul * base % MOD\n",
    "            \n",
    "            if prefix == suffix:\n",
    "                happy = i+1\n",
    "        \n",
    "        return s[:happy]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        prefix, suffix = 0, 0\n",
    "        base, mod, mul = 31, 1000000007, 1\n",
    "        happy = 0\n",
    "        for i in range(1, n):\n",
    "            prefix = (prefix * base + (ord(s[i - 1]) - 97)) % mod\n",
    "            suffix = (suffix + (ord(s[n - i]) - 97) * mul) % mod\n",
    "            if prefix == suffix:\n",
    "                happy = i\n",
    "            mul = mul * base % mod\n",
    "        return s[:happy]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        base = 31\n",
    "        mul = 1\n",
    "        ans = -1\n",
    "        n = len(s)\n",
    "        pre,suf = 0, 0\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        for i in range(n-1):\n",
    "            pre = (pre * base + ord(s[i]) - ord('a')) % mod\n",
    "            suf = (suf + (ord(s[n-1-i]) - ord('a')) * mul) % mod\n",
    "            if pre == suf:\n",
    "                ans = max(ans, i)\n",
    "            mul = mul * base % mod\n",
    "        \n",
    "        if ans == -1:\n",
    "            return \"\"\n",
    "        else:\n",
    "            return s[:ans+1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        base = 31\n",
    "        mod = 2**31 - 1\n",
    "        mul = 1\n",
    "        ans = 0\n",
    "        _hash = lambda i: ord(s[i]) - ord('a')\n",
    "\n",
    "        prefix_hash = suffix_hash = 0\n",
    "        for i in range(n - 1): # 整个字符不用算，不包括自己\n",
    "            prefix_hash = (prefix_hash * base + _hash(i)) % mod\n",
    "            suffix_hash = (_hash(n - 1 - i) * mul + suffix_hash) % mod\n",
    "            mul = mul * base % mod\n",
    "            if prefix_hash == suffix_hash: # 不能马上返回，因为可能有更长的\n",
    "                ans = i + 1 \n",
    "\n",
    "        return s[:ans]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        base = 31\n",
    "        mod = 2**31 - 1\n",
    "        mul = 1\n",
    "        last_match_idx = 0\n",
    "        _hash = lambda i: ord(s[i]) - ord('a')\n",
    "\n",
    "        prefix_hash = suffix_hash = 0\n",
    "        for i in range(n - 1): # 整个字符不用算，不包括自己\n",
    "            prefix_hash = (prefix_hash * base + _hash(i)) % mod\n",
    "            suffix_hash = (_hash(n - 1 - i) * mul + suffix_hash) % mod\n",
    "            mul = mul * base % mod\n",
    "            if prefix_hash == suffix_hash: # 不能马上返回，因为可能有更长的\n",
    "                last_match_idx = i + 1\n",
    "\n",
    "        return s[:last_match_idx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        MOD = 10**9+7\n",
    "        base = 31\n",
    "\n",
    "        def encode(ch):\n",
    "            return ord(ch)-ord('a')+1\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        l, r = 0, 0\n",
    "        mul = 1\n",
    "        ans = 0\n",
    "        for i in range(n-1):\n",
    "            l = (l*base+encode(s[i]))%MOD\n",
    "            r = (r+encode(s[-i-1])*mul)%MOD\n",
    "            mul = mul*base%MOD\n",
    "            if l==r: ans = i+1\n",
    "        \n",
    "        return s[:ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        \"\"\"\n",
    "        前缀：以首字母开头，不包含尾字母的连续子串\n",
    "        例如 s = 'abc' 则其前缀有'a', 'ab'。'abc'不是他的前缀，因为包含了尾字母\n",
    "        后缀：同理，s的后缀有'c', 'bc'\n",
    "        \"\"\"\n",
    "        return self._longestPrefix(s)\n",
    "\n",
    "    def _longestPrefix(self, s: str) -> str:\n",
    "        \"\"\"\n",
    "        暴力法\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        for length in range(n-1, 0, -1):\n",
    "            prefix = s[:length]\n",
    "            suffix = s[n-length:]\n",
    "            if prefix == suffix:\n",
    "                return prefix\n",
    "        return ''\n",
    "    \n",
    "# if __name__ == '__main__':\n",
    "#     print(Solution().longestPrefix(s='level'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        l,r=s[:-1],s[1:]\n",
    "        while l and r and l!=r:l,r=l[:-1],r[1:]\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        x, p = 41, 10**9+7\n",
    "        a = [ord(c) - ord('a') +1 for c in s]\n",
    "        prefix, suffix, ans =  0, 0, -1\n",
    "        for i in range(len(a)-1):\n",
    "            prefix, suffix = (prefix*x + a[i])%p, (suffix + a[-i-1]*pow(x, i, p))%p\n",
    "            if prefix == suffix: ans = i \n",
    "        return s[:ans+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        res = \"\"\n",
    "        if len(s) == 1:\n",
    "            return \"\"\n",
    "        if s[0] == s[-1]:\n",
    "            res = s[0]\n",
    "        n = len(s)\n",
    "        for i in range(1,n):\n",
    "            #前缀\n",
    "            qianzhui = (s[:i])\n",
    "            houzhui = (s[-i:])\n",
    "            if qianzhui == houzhui:\n",
    "                res = qianzhui\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        a2h = {\n",
    "            a: i for a, i in zip('abcdefghijklmnopqrstuvwxyz', [\n",
    "                1, 3, 5, 7, 11, 13, 19, 23, 29, 31, 37, 41, 43, 47, 49, 51, 53, 57, 59, 61, 63, 67, 71, 73, 77, 79,\n",
    "            ])\n",
    "        }\n",
    "        mod = 10 ** 5 + 7\n",
    "        l = len(s)\n",
    "        end = 0\n",
    "        prefix_hash = 0\n",
    "        postfix_hash = 0\n",
    "        happy_prefix = ''\n",
    "        while end < l - 1:\n",
    "            prefix_hash += a2h[s[end]]\n",
    "            prefix_hash %= mod\n",
    "            postfix_hash += a2h[s[l - end - 1]]\n",
    "            postfix_hash %= mod\n",
    "            if prefix_hash == postfix_hash and s[:end + 1] == s[l - end - 1:]:\n",
    "                happy_prefix = s[:end + 1]\n",
    "            end += 1\n",
    "        return happy_prefix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        len_s = len(s)\n",
    "        longestHappyPrefix = ''\n",
    "        for i in range(1, len_s):\n",
    "            curentPrefix = s[:i]\n",
    "            if curentPrefix == s[-i:]:\n",
    "                longestHappyPrefix = curentPrefix\n",
    "        return longestHappyPrefix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n=len(s)\n",
    "        ans=''\n",
    "        if len(s)==1:\n",
    "            return ans\n",
    "        if s[0]==s[-1]:\n",
    "            ans=s[0]\n",
    "        for i in range(1,n-1):\n",
    "            tmp1=s[:i+1]\n",
    "            tmp2=s[n-i-1:n]\n",
    "            if tmp1==tmp2:\n",
    "                ans=tmp1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        result=''\n",
    "        for i in range(len(s)):\n",
    "            prefix = s[:i]\n",
    "            afterfix = s[-i:]\n",
    "            if prefix == afterfix:\n",
    "                result = prefix\n",
    "        return result\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        mod = pow(10, 9) + 7\n",
    "        base = 31\n",
    "        mul = 1\n",
    "        n = len(s)\n",
    "        pre, suf = 0, 0\n",
    "        possible = []\n",
    "        for i in range(n - 1):\n",
    "            pre = (pre * base + ord(s[i]) - 97) % mod\n",
    "            suf = (suf + (ord(s[-i - 1]) - 97) * mul) % mod\n",
    "            if pre == suf:\n",
    "                possible.append(i + 1)\n",
    "            \n",
    "            mul = (mul * base) % mod\n",
    "        if possible:\n",
    "            return s[: possible[-1]]\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        f = [0] * (n + 1)\n",
    "        f[0], i, j = -1, 0, -1\n",
    "        \n",
    "        while i < n:\n",
    "            while j != -1 and s[i] != s[j]:\n",
    "                j = f[j]\n",
    "            i += 1\n",
    "            j += 1\n",
    "            f[i] = j\n",
    "        return s[:f[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        s = s + \"?\"\n",
    "        nextA = [None]*len(s)\n",
    "        nextA[0] = -1\n",
    "        k = -1\n",
    "        j = 0\n",
    "        while j < len(s) - 1: \n",
    "            #s[k]表示前缀，s[j]表示后缀  \n",
    "            if k == -1 or s[j] == s[k]:\n",
    "                k += 1  \n",
    "                j += 1\n",
    "                nextA[j] = k\n",
    "            else:   \n",
    "                k = nextA[k]   \n",
    "            \n",
    "\n",
    "        #print(nextA)\n",
    "\n",
    "        return s[:nextA[-1]]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        mod = pow(10, 9) + 7\n",
    "        base = 31\n",
    "        mul = 1\n",
    "        n = len(s)\n",
    "        pre, suf = 0, 0\n",
    "        possible = []\n",
    "        for i in range(n - 1):\n",
    "            pre = (pre * base + ord(s[i]) - 97) % mod\n",
    "            suf = (suf + (ord(s[-i - 1]) - 97) * mul) % mod\n",
    "            if pre == suf:\n",
    "                possible.append(i + 1)\n",
    "            \n",
    "            mul = (mul * base) % mod\n",
    "        for x in reversed(possible):\n",
    "            pre = s[: x]\n",
    "            suf = s[-x: ]\n",
    "            if pre == suf:\n",
    "                return s[: possible[-1]]\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        mod = pow(10, 9) + 7\n",
    "        base = 31\n",
    "        mul = 1\n",
    "        n = len(s)\n",
    "        pre, suf = 0, 0\n",
    "        possible = []\n",
    "        for i in range(n - 1):\n",
    "            pre = (pre * base + ord(s[i]) - 97) % mod\n",
    "            suf = (suf + (ord(s[-i - 1]) - 97) * mul) % mod\n",
    "            if pre == suf:\n",
    "                possible.append(i + 1)\n",
    "            \n",
    "            mul = (mul * base) % mod\n",
    "        for x in reversed(possible):\n",
    "            pre = s[: x]\n",
    "            suf = s[-x: ]\n",
    "            if pre == suf:\n",
    "                return s[: possible[-1]]\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "\n",
    "        n=len(s)\n",
    "        next=[0]*n\n",
    "        res=0\n",
    "        for i in range(1,n):\n",
    "            if s[:i]==s[-i:]:\n",
    "                res=i\n",
    "        \n",
    "        return s[:res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        mod = pow(10, 9) + 7\n",
    "        base = 31\n",
    "        mul = 1\n",
    "        n = len(s)\n",
    "        pre, suf = 0, 0\n",
    "        possible = []\n",
    "        for i in range(n - 1):\n",
    "            pre = (pre * base + ord(s[i]) - 97) % mod\n",
    "            suf = (suf + (ord(s[-i - 1]) - 97) * mul) % mod\n",
    "            if pre == suf:\n",
    "                possible.append(i + 1)\n",
    "            \n",
    "            mul = (mul * base) % mod\n",
    "        for x in reversed(possible):\n",
    "            pre = s[: x]\n",
    "            suf = s[-x: ]\n",
    "            if pre == suf:\n",
    "                return s[: possible[-1]]\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        t = s[: -1] + '#' + s + '$'\n",
    "        nx = [-1]\n",
    "        j = 0\n",
    "        for i in range(1, len(t)):\n",
    "            if t[i] != t[j]:\n",
    "                nx.append(j)\n",
    "                while j != -1 and t[i] != t[j]:\n",
    "                    j = nx[j]\n",
    "            else:\n",
    "                nx.append(nx[j])\n",
    "            j += 1\n",
    "        return s[: nx[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        dp = [-1, 0]\n",
    "        for i in range(1, n):\n",
    "            last = dp[-1]\n",
    "            while last >= 0 and s[last] != s[i]:\n",
    "                last = dp[last]\n",
    "            dp.append(last + 1)\n",
    "        return s[:dp[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        \n",
    "        base=29\n",
    "        mod = 10**9+7\n",
    "\n",
    "        tmp = 0\n",
    "        n1 = 0\n",
    "        n2 = 0\n",
    "        n = len(s)\n",
    "        s = [ord(i)-ord('a') for i in s]\n",
    "        for i in range(0,len(s)-1):\n",
    "            n1 = (n1*base+s[i])%mod\n",
    "            n2 = (n2+s[n-1-i]*pow(base,i,mod))%mod\n",
    "            if n1==n2:\n",
    "                tmp = i+1\n",
    "        \n",
    "        return ''.join(chr(i+97) for i in s[:tmp])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        b1, b2 = 26, 27\n",
    "        mod1, mod2 = 10**9+7, 10**9+9\n",
    "        os = s\n",
    "        s2 = [ord(c) - ord('a') for c in s]\n",
    "        s = s2\n",
    "        h11, h12 = 0, 0\n",
    "        h21, h22 = 0, 0\n",
    "        m1, m2 = 1, 1\n",
    "        res = 0\n",
    "        for i in range(len(s) - 1):\n",
    "            #s1 0:i s2 n-1-i:n-1\n",
    "            h11 = (h11 + m1 * s[i]) % mod1\n",
    "            h12 = (h12 + m2 * s[i]) % mod2\n",
    "\n",
    "            h21 = (h21 * b1 + s[len(s) - 1 -i]) % mod1\n",
    "            h22 = (h22 * b2 + s[len(s) - 1 -i]) % mod2\n",
    "            m1 = (m1 * b1) % mod1\n",
    "            m2 = (m2 * b2) % mod2\n",
    "            #print(h11, h12, h21, h22)\n",
    "            if h11 == h21 and h12 == h22:\n",
    "                res = i + 1\n",
    "        return os[:res]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        if not s or len(s) == 1:\n",
    "            return \"\"\n",
    "        s_list = list(s)\n",
    "        s_table = [0] * len(s)\n",
    "\n",
    "        k = 0\n",
    "        for j in range(1, len(s), 1):\n",
    "            if s_list[j] == s_list[k]:\n",
    "                k += 1\n",
    "            else:\n",
    "                while k > 0 and s_list[j] != s_list[k]:\n",
    "                    k = s_table[k-1]\n",
    "                if s_list[j] == s_list[k]:\n",
    "                    k += 1\n",
    "\n",
    "            s_table[j] = k\n",
    "\n",
    "        max_count = s_table[-1]\n",
    "        index = s_table.index(max_count)\n",
    "        return s[index - max_count + 1: index+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        ans=\"\"\n",
    "        q=0\n",
    "        h=0\n",
    "        a=s\n",
    "        l=len(a)\n",
    "        t=[]\n",
    "        mo=10**9+7\n",
    "        for i in range(l-1):\n",
    "            q=(q*26+ord(a[i])-97)%mo\n",
    "            h=(h+(ord(a[-1-i])-97)*pow(26,i,mo))%mo\n",
    "            if q==h:\n",
    "                t.append(i)\n",
    "        for i in t[::-1]:\n",
    "            if a[:i+1]==a[-1-i:]:\n",
    "                return a[:i+1]\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        letd = {chr(i): [] for i in range(97, 123)}\n",
    "        for i in range(n):\n",
    "            letd[s[i]].append(i)\n",
    "        i = 1\n",
    "        while i < n:\n",
    "            for j in range(n-i):\n",
    "                if s[j] != s[j+i]:\n",
    "                    x = bisect.bisect(letd[s[j]], j+i)\n",
    "                    if x == len(letd[s[j]]):\n",
    "                        i1 = n - j\n",
    "                    else:\n",
    "                        i1 = letd[s[j]][x] - j\n",
    "                    y = bisect.bisect(letd[s[j+i]], j)\n",
    "                    if not y:\n",
    "                        i2 = i+j+1\n",
    "                    else:\n",
    "                        i2 = i+j-letd[s[i+j]][y-1]\n",
    "                    i = max(i1, i2)\n",
    "                    \n",
    "                    break\n",
    "            else:\n",
    "                return s[i:]    \n",
    "        \n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def longestPrefix(self, s: str) -> str:\n",
    "#         n = len(s)\n",
    "#         if n <= 1:\n",
    "#             return ''\n",
    "#         for i in range(1,n):\n",
    "#             if s[i] == s[0]:\n",
    "#                 if s[:n-i] == s[i:]:\n",
    "#                     return s[i:]\n",
    "#         return ''\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        # ans  = \"\"\n",
    "        # for i in range(len(s)):\n",
    "        #     # print(s[:i], s[len(s)-i:])\n",
    "        #     if s[:i] == s[len(s)-i:]:\n",
    "        #         ans = s[:i]\n",
    "        # return ans\n",
    "\n",
    "        if not s:\n",
    "            return None\n",
    "        def getNextArr(str_):\n",
    "            if len(str_) == 1:\n",
    "                return [-1]\n",
    "            next_arr = [0] * (len(str_) + 1)\n",
    "            next_arr[0],next_arr[1] = -1,0\n",
    "            pos,cn = 2, 0\n",
    "            while pos < len(next_arr):\n",
    "                if str_[pos-1] == str_[cn]:\n",
    "                    next_arr[pos] = cn + 1\n",
    "                    pos,cn = pos + 1, cn + 1\n",
    "                elif cn > 0:\n",
    "                    cn = next_arr[cn]\n",
    "                else:\n",
    "                    next_arr[pos] = 0\n",
    "                    pos += 1\n",
    "            return next_arr\n",
    "        next_arr = getNextArr(list(s))\n",
    "        return s[:next_arr[-1]]\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def longestPrefix(self, s: str) -> str:\n",
    "#         l, r = 0, len(s) - 1 # 左右指针\n",
    "#         ls, rs = '', '' # 用于存储左右指针扫描过的字符\n",
    "#         ret = '' # 最长快乐前缀\n",
    "#         while l < len(s) and r >= 0:\n",
    "#             lmove, rmove = False, False # 用两个布尔变量控制左右指针是否应该移动\n",
    "#             if len(ls) == len(rs): \n",
    "#                 if ls == rs and ls != s: ret = ls # 如果前缀和后缀相等，保存为快乐前缀\n",
    "#                 lmove = True\n",
    "#                 rmove = True\n",
    "#             elif len(ls) < len(rs): lmove = True # 如果前缀比后缀短，那么移动左指针\n",
    "#             else: rmove = True # 否则移动右指针\n",
    "                \n",
    "#             if lmove:\n",
    "#                 while l < len(s) and s[l] != s[-1]: # 左指针负责寻找字符串中与字符串结尾字符相等的字符\n",
    "#                     ls += s[l]\n",
    "#                     l += 1\n",
    "#                 ls += s[l]\n",
    "#                 l += 1\n",
    "#             if rmove:\n",
    "#                 while r >= 0 and s[r] != s[0]: # 右指针负责寻找字符串中与字符串开始字符相等的字符\n",
    "#                     rs = s[r] + rs\n",
    "#                     r -= 1\n",
    "#                 rs = s[r] + rs\n",
    "#                 r -= 1\n",
    "#         return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        dp = [-1] + [0] * n\n",
    "        for i in range(1, n+1):\n",
    "            tmp = dp[i-1]\n",
    "            while tmp != -1 and s[tmp] != s[i-1]:\n",
    "                tmp = dp[tmp]\n",
    "            dp[i] = tmp + 1\n",
    "        return s[0:dp[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n=len(s)-1\n",
    "        if n==0:\n",
    "            return \"\"\n",
    "        else:\n",
    "            a=list(range(1,n+1))[::-1]\n",
    "            for i in a:\n",
    "            \n",
    "                if s[:i]==s[-i:]:\n",
    "\n",
    "                  \n",
    "                    return s[:i]\n",
    "            else:\n",
    "                return ''\n",
    "                \n",
    "                   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        # ans=''\n",
    "        # for i in range(1,len(s)):\n",
    "        #     if s[:i]==s[-i:]:\n",
    "        #         ans=s[:i]\n",
    "        #     #print(s[:i])\n",
    "        # return ans\n",
    "        n=[0 for i in range(len(s))]\n",
    "        k,n[0]=-1,-1\n",
    "        if len(s)<2:return ''\n",
    "        for i in range(1,len(s)):\n",
    "            while k>-1 and s[k+1]!=s[i]:\n",
    "                k=n[k]\n",
    "            if s[k+1]==s[i]:k+=1\n",
    "            n[i]=k\n",
    "        print(n)\n",
    "        if k==-1:return ''\n",
    "        return s[:k+1]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        # for i in range(1, len(s)):\n",
    "        #     if s[i]!=s[0]: continue\n",
    "        #     if s[i:]==s[:(len(s)-i)]:\n",
    "        #         return s[i:]\n",
    "        # return \"\"\n",
    "        n = len(s)\n",
    "        fail = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            j = fail[i - 1]\n",
    "            while j != -1 and s[j + 1] != s[i]:\n",
    "                j = fail[j]\n",
    "            if s[j + 1] == s[i]:\n",
    "                fail[i] = j + 1\n",
    "\n",
    "        return s[:fail[-1] + 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        next_list = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            j = next_list[i - 1]\n",
    "            while j != -1 and s[j + 1] != s[i]:\n",
    "                j = next_list[j]\n",
    "            if s[j + 1] == s[i]:\n",
    "                next_list[i] = j + 1\n",
    "        return s[:next_list[-1] + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        fail = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            j = fail[i - 1]\n",
    "            while j != -1 and s[j + 1] != s[i]:\n",
    "                j = fail[j]\n",
    "            if s[j + 1] == s[i]:\n",
    "                fail[i] = j + 1\n",
    "\n",
    "        return s[:fail[-1] + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n < 2: return ''\n",
    "        nextl = [0] * (n+1)\n",
    "        s = ' ' + s\n",
    "        i, j = 2, 0\n",
    "        while i <= n:\n",
    "            while j and s[i] != s[j+1]: j = nextl[j]\n",
    "            if s[i] == s[j+1]: j += 1\n",
    "            nextl[i] = j\n",
    "            i += 1\n",
    "        # print(nextl)\n",
    "        if nextl[-1] == 0: return ''\n",
    "        else: return s[1:nextl[-1]+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        fail = [0] * n\n",
    "        j = 0\n",
    "        for i in range(1, n):\n",
    "            while j > 0 and s[j] != s[i]:\n",
    "                j = fail[j - 1]\n",
    "            if s[j] == s[i]:\n",
    "                j += 1\n",
    "            fail[i] = j\n",
    "\n",
    "        return s[:fail[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        nextt = [-1] * (len(s)+1)\n",
    "        t = nextt[0]\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if t == -1 or s[t] == s[i]:\n",
    "                t += 1\n",
    "                i += 1\n",
    "                nextt[i] = t\n",
    "            else:\n",
    "                t = nextt[t]\n",
    "        return s[:nextt[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_next(self, T):\n",
    "        n = len(T)\n",
    "        nxt = [0] * (n+1)\n",
    "        nxt[0] = -1\n",
    "        i, j = 0, -1\n",
    "        while i < n: \n",
    "            if j == -1 or T[i] == T[j]:\n",
    "                i, j = i+1, j+1\n",
    "                nxt[i] = j\n",
    "            else:\n",
    "                j = nxt[j]\n",
    "        return nxt\n",
    "\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        nxt =  self.get_next(s)\n",
    "        return s[:nxt[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        fail = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            j = fail[i-1]\n",
    "            while j != -1 and s[j+1] != s[i]:\n",
    "                j = fail[j]\n",
    "            if s[j+1] == s[i]:\n",
    "                fail[i] = j + 1\n",
    "        return s[:fail[-1]+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        s += \"#\"\n",
    "        n = len(s)\n",
    "        if n == 1:\n",
    "            return \"\"\n",
    "        nxt = [-1]*n\n",
    "        k = -1\n",
    "        j = 0\n",
    "        while j < n - 1:\n",
    "            if k == -1 or s[k] == s[j]:\n",
    "                k+=1\n",
    "                j+=1\n",
    "                nxt[j] = k\n",
    "            else:\n",
    "                k = nxt[k]\n",
    "        return s[:nxt[n-1]]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        # 将字符串的前缀字符串hash化\n",
    "        # 把每一类字符看作一个数，有n种字符就取n进制（实际base > n且取质数）\n",
    "        # 为防止越界取一个较大质数的mod，如10**9 + 7/9\n",
    "        # 也可计算两个hash，减小重复概率\n",
    "        # base = 29\n",
    "        # mod = 10**9 + 7\n",
    "        # n = len(s)\n",
    "        # # pre_hash[i] = hash(s[:i])\n",
    "        # # suf_hash[i] = hash(s[i:])\n",
    "        # pre_hash = suf_hash = 0\n",
    "        # power = 1\n",
    "        # cur = 0\n",
    "        # ans = 0\n",
    "        # while cur < len(s) - 1:  \n",
    "        #     pre_hash = (pre_hash * base + ord(s[cur]) - ord('a')) % mod\n",
    "        #     suf_hash = (suf_hash + (ord(s[n - 1 - cur]) - ord('a')) * power) % mod\n",
    "        #     if pre_hash == suf_hash:\n",
    "        #         ans = cur + 1\n",
    "        #     power = (power * base) % mod  # 注意取模减小运算量\n",
    "        #     cur += 1\n",
    "        # return s[:ans]\n",
    "\n",
    "        # KMP解法\n",
    "        n = len(s)\n",
    "        kmp = [0] * n\n",
    "        for i in range(1, n):\n",
    "            j = i - 1\n",
    "            while j >= 0 and s[i] != s[kmp[j]]:\n",
    "                j = kmp[j] - 1\n",
    "            if j < 0:\n",
    "                kmp[i] = 0\n",
    "            else:\n",
    "                kmp[i] = kmp[j] + 1\n",
    "        # print(kmp)\n",
    "        return(s[:kmp[-1]])\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        j = 0\n",
    "        pi = [0] * n\n",
    "        for i in range(1, n):\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = pi[j - 1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            pi[i] = j\n",
    "        \n",
    "        return s[:pi[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        pi = [-1]*(n+1)\n",
    "        p,q = 0,-1\n",
    "        while p < n:\n",
    "            if q == -1 or s[p] == s[q]:\n",
    "                p += 1\n",
    "                q += 1\n",
    "                pi[p] = q\n",
    "            else:\n",
    "                q = pi[q]\n",
    "        return s[:pi[-1]]\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            if s[:i + 1] == s[n - i - 1:]:\n",
    "                dp[i + 1] = i + 1\n",
    "            else:\n",
    "                dp[i + 1] = dp[i]\n",
    "\n",
    "        return s[:max(dp[:-1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "      n=len(s)\n",
    "      nex=[0]\n",
    "      i=0\n",
    "      j=1\n",
    "      while j<n:\n",
    "        if s[i] == s[j]:\n",
    "          i+=1\n",
    "          j+=1\n",
    "          nex.append(i)\n",
    "        elif i:\n",
    "          i=nex[i-1]\n",
    "        else:\n",
    "          j+=1\n",
    "          nex.append(0)\n",
    "      return s[:nex[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        table = [-1, 0] \n",
    "        # table[i]: s[0:i] 的最长快乐前缀长度\n",
    "        l = len(s)\n",
    "        for i in range(2, l+1):\n",
    "            k = table[i-1]\n",
    "            while s[k] != s[i-1]:\n",
    "                k = table[k]\n",
    "                if k < 0:\n",
    "                    break\n",
    "            table.append(k + 1)\n",
    "        return s[0:table[-1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        next = [0 for _ in range(len(s))]\n",
    "        j = 0\n",
    "        for i in range(1, len(s)):\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = next[j - 1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            next[i] = j\n",
    "        return s[:next[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        lastIndex = self._get_next(s)\n",
    "        if(lastIndex != -1):\n",
    "            return s[:lastIndex]\n",
    "        return \"\"\n",
    "\n",
    "    def _get_next(self,s:str):\n",
    "        i = 0\n",
    "        j = -1\n",
    "        next = [-1]\n",
    "\n",
    "        while i < len(s):\n",
    "            if j == -1 or s[i] == s[j]:\n",
    "                i+=1\n",
    "                j+=1\n",
    "                next.insert(i,j)\n",
    "            else:\n",
    "                j = next[j]\n",
    "        return next[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        ne = [-1] + [0] * len(s)\n",
    "        i, j = 0, -1\n",
    "        while i < len(s):\n",
    "            if j == -1 or s[i] == s[j]:\n",
    "                i, j = i + 1, j + 1\n",
    "                ne[i] = j\n",
    "            else: j = ne[j]\n",
    "        return s[:ne[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        l = len(s)\n",
    "        table = [0]*(l+1)\n",
    "        table[0] = -1\n",
    "        # table[i]: s[0:i] 的最长快乐前缀长度\n",
    "        for i in range(2, l+1):\n",
    "            k = table[i-1]\n",
    "            while s[k] != s[i-1]:\n",
    "                k = table[k]\n",
    "                if k < 0:\n",
    "                    break\n",
    "            table[i] = k + 1\n",
    "        return s[0:table[-1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        fail = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            j = fail[i - 1]\n",
    "            while j != -1 and s[j + 1] != s[i]:\n",
    "                j = fail[j]\n",
    "            if s[j + 1] == s[i]:\n",
    "                fail[i] = j + 1\n",
    "\n",
    "        return s[:fail[-1] + 1]\n",
    "\n",
    "\n",
    "        ans = \"\"\n",
    "        for i in range(1,len(s)):\n",
    "            if s[:i]==s[-i:]:\n",
    "                ans = s[:i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        next_arr = [0]*len(s)\n",
    "        j = 0\n",
    "        for i in range(1,len(s)):\n",
    "            while j>0 and s[i] != s[j]:\n",
    "                j = next_arr[j-1] \n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            next_arr[i] = j\n",
    "        return s[ :next_arr[-1] ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        j = 0\n",
    "        pi = [0] * n\n",
    "        for i in range(1, n):\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = pi[j - 1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            pi[i] = j\n",
    "        \n",
    "        return s[:pi[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        s_len = len(s)\n",
    "        fail = [-1] * s_len\n",
    "\n",
    "        for i in range(1, s_len):\n",
    "            j = fail[i - 1]\n",
    "            while j >= 0 and s[j + 1] != s[i]:\n",
    "                j = fail[j]\n",
    "            if s[j + 1] == s[i]:\n",
    "                fail[i] = j + 1\n",
    "        \n",
    "        return s[:fail[s_len - 1] + 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        next = [0] * n\n",
    "        j = 0\n",
    "        for i in range(1, n):\n",
    "            while j > 0 and s[j] != s[i]:\n",
    "                j = next[j - 1]\n",
    "            if s[j] == s[i]:\n",
    "                j += 1\n",
    "            next[i] = j\n",
    "        return s[:next[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        pi = [0] * len(s)\n",
    "        for i in range(1,len(s)):\n",
    "            j  =  pi[i-1]\n",
    "            while j > 0  and s[i] != s[j]:\n",
    "                j = pi[j-1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            pi[i] = j\n",
    "        return s[:pi[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        nxt = [0] * n\n",
    "        now = 0\n",
    "        for i in range(1, n):\n",
    "            while now > 0 and s[now] != s[i]:\n",
    "                now = nxt[now - 1]\n",
    "            if s[now] == s[i]:\n",
    "                now += 1\n",
    "            nxt[i] = now\n",
    "        return s[:nxt[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        f = [0] * n\n",
    "        j = 0\n",
    "        for i in range(1, n):\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = f[j - 1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            f[i] = j\n",
    "        return s[:j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n=len(s)\n",
    "        l,r=-1,-2\n",
    "        z=[0]*n\n",
    "        ans=0\n",
    "        for i in range(1,n):\n",
    "            if i<r:\n",
    "                z[i]=min(r-i,z[i-l])\n",
    "            while i+z[i]<n and s[z[i]]==s[i+z[i]]:\n",
    "                z[i]+=1\n",
    "            if z[i]>r:\n",
    "                l=i\n",
    "                r=i+z[i]\n",
    "            if z[i]==n-i:\n",
    "                return s[i:]\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        fail = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            j = fail[i - 1]\n",
    "            while j != -1 and s[j + 1] != s[i]:\n",
    "                j = fail[j]\n",
    "            if s[j + 1] == s[i]:\n",
    "                fail[i] = j + 1\n",
    "        return s[:fail[-1] + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        res = [0] * len(s)\n",
    "\n",
    "        for i in range(1,len(s)):\n",
    "            pos = res[i-1]\n",
    "            res_i = i-1\n",
    "            while pos >0 and s[pos]!=s[i]:\n",
    "                res_i = pos-1\n",
    "                pos = res[pos-1]\n",
    "                 \n",
    "            if pos>0:\n",
    "                res[i] = res[res_i]+1\n",
    "            elif pos==0 and s[pos]==s[i]:\n",
    "                res[i] =res[res_i]+1\n",
    "        \n",
    "        return s[:res[-1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        nxt = [0]\n",
    "        x = 1\n",
    "        now = 0\n",
    "        while x < n:\n",
    "            if s[now] == s[x]:\n",
    "                now += 1\n",
    "                x += 1\n",
    "                nxt.append(now)\n",
    "            elif now:\n",
    "                now = nxt[now-1]\n",
    "            else:\n",
    "                nxt.append(0)\n",
    "                x += 1\n",
    "        return s[:nxt[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n=len(s)\n",
    "        arr=[0]\n",
    "        for i in range(1,n):\n",
    "            j=arr[-1]\n",
    "            while j>0 and s[i]!=s[j]:\n",
    "                j=arr[j-1]\n",
    "            if s[i]==s[j]:\n",
    "                j+=1\n",
    "            arr.append(j)\n",
    "        return s[:arr[-1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, p: str) -> str:\n",
    "        table=[0]\n",
    "        for i in range(1,len(p)):\n",
    "            newE=p[i]\n",
    "            nowPos=table[i-1]\n",
    "            if newE==p[nowPos]: table.append(nowPos+1)\n",
    "            else:\n",
    "                while True:\n",
    "                    if nowPos==0: \n",
    "                        table.append(0)\n",
    "                        break\n",
    "                    nowPos=table[nowPos-1]\n",
    "                    if newE==p[nowPos]: \n",
    "                        table.append(nowPos+1)\n",
    "                        break\n",
    "        # print(p+\"'s table:\")\n",
    "        # print(table,end=\"\\n\")\n",
    "        return p[0:table[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        nxt = [-1]*n\n",
    "        for i in range(1,n):\n",
    "            j = nxt[i-1]\n",
    "            while j!=-1 and s[i] != s[j+1]:\n",
    "                j = nxt[j]\n",
    "            if s[i] == s[j+1]:\n",
    "                nxt[i] = j+1\n",
    "        return s[:nxt[-1]+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "       \n",
    "\n",
    "        # leetcode\n",
    "        # nex = [-1]*n\n",
    "        # for i in range(1, n):\n",
    "        #     j = nex[i-1]\n",
    "        #     while j!=-1 and s[j+1] != s[i]:\n",
    "        #         j = nex[j]\n",
    "        #     if s[j+1] == s[i]:\n",
    "        #         nex[i]=j+1\n",
    "        # return s[: nex[-1]+1]\n",
    "        # my\n",
    "        nex = [0]*n\n",
    "        i = 0\n",
    "        j = 1\n",
    "\n",
    "        while j < n:\n",
    "            while i > 0 and s[i] != s[j]:\n",
    "                i = nex[i-1]\n",
    "            if i == 0 and s[i] != s[j]:\n",
    "                nex[j] = 0\n",
    "                j+=1\n",
    "                continue\n",
    "            while j < n and s[i] == s[j]:\n",
    "                i+=1\n",
    "                nex[j] = i\n",
    "                j+=1\n",
    "        return s[:nex[-1]]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        pi = [0] * n\n",
    "        j = 0\n",
    "        for i in range(1, n):\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = pi[j - 1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            pi[i] = j\n",
    "        \n",
    "        return s[:pi[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        def kmp(s):\n",
    "            n = len(s)\n",
    "            nxt = [0] * n \n",
    "            j = 0 \n",
    "            for i in range(1, n):\n",
    "                while j > 0 and s[i] != s[j]:\n",
    "                    j = nxt[j-1]\n",
    "                if s[i] == s[j]:\n",
    "                    j += 1\n",
    "                nxt[i] = j\n",
    "\n",
    "            return nxt\n",
    "        n = len(s)\n",
    "        nxt = kmp(s)\n",
    "        return s[:nxt[-1]]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestPrefix(self, s: str) -> str:\r\n",
    "        next,n = [0]*len(s),len(s)\r\n",
    "        i,j = 1,0\r\n",
    "        while i < n:\r\n",
    "            if s[i] == s[j]:\r\n",
    "                next[i] = j+1\r\n",
    "                i += 1\r\n",
    "                j += 1\r\n",
    "            else:\r\n",
    "                if j == 0:\r\n",
    "                    next[i] = 0\r\n",
    "                    i += 1\r\n",
    "                else:\r\n",
    "                    j = next[j-1]\r\n",
    "        return s[0:next[-1]]\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "\n",
    "        n = len(s)\n",
    "        pi = [0] * n\n",
    "        \n",
    "        j = 0\n",
    "        for i in range(1, n):\n",
    "            while j>0 and s[i] != s[j]:     # 当前位置s[i]与s[j]不等\n",
    "                j = pi[j-1]                 # j指向之前位置，s[i]与s[j]继续比较\n",
    "\n",
    "            if s[i] == s[j]:                # s[i]与s[j]相等，j+1，指向后一位\n",
    "                j += 1\n",
    "            \n",
    "            pi[i] = j\n",
    "        \n",
    "        return s[:pi[-1]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        fail = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            j = fail[i - 1]\n",
    "            while j != -1 and s[j + 1] != s[i]:\n",
    "                j = fail[j]\n",
    "            if s[j + 1] == s[i]:\n",
    "                fail[i] = j + 1\n",
    "\n",
    "        return s[:fail[-1] + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        match = [0]\n",
    "        c = 0\n",
    "        for v in s[1:]:\n",
    "            while c and v!=s[c]:\n",
    "                c = match[c-1]\n",
    "            if v==s[c]:\n",
    "                c += 1\n",
    "            match.append(c)\n",
    "        return s[:match[-1]]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        nxt = [-1]*n\n",
    "        for i in range(1,n):\n",
    "            j = nxt[i-1]\n",
    "            while j!=-1 and s[j+1]!=s[i]:\n",
    "                j = nxt[j]\n",
    "            if s[j+1] == s[i]:\n",
    "                nxt[i] = j+1\n",
    "        print(nxt)\n",
    "        return s[:nxt[-1]+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        nxt = [-1]*len(s)\n",
    "        nxt[0] = 0\n",
    "        now = 0\n",
    "        x = 1\n",
    "        while x < len(s):\n",
    "            if s[now] == s[x]:\n",
    "                now += 1\n",
    "                nxt[x] = now\n",
    "                x += 1\n",
    "            elif now > 0:\n",
    "                now = nxt[now-1]\n",
    "            else:\n",
    "                nxt[x] = 0\n",
    "                x += 1\n",
    "        start = nxt[-1]\n",
    "        print(nxt)\n",
    "        if start == len(s) or start == 0:\n",
    "            return \"\"\n",
    "        return s[:start]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        fail = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            j = fail[i - 1]\n",
    "            while j != -1 and s[j + 1] != s[i]:\n",
    "                j = fail[j]\n",
    "            if s[j + 1] == s[i]:\n",
    "                fail[i] = j + 1\n",
    "\n",
    "        print(fail)\n",
    "        return s[:fail[-1] + 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPrefix(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        f = [-1] * (n + 1)\n",
    "        j = 0\n",
    "        for i in range(1, n + 1):\n",
    "            j = f[i - 1]\n",
    "            while j != -1 and s[i - 1] != s[j]:\n",
    "                j = f[j]\n",
    "            f[i] = j + 1\n",
    "        print(f)\n",
    "        return s[:f[n]]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
